package roaring

import (
	
	
	
	
)

var defaultWorkerCount = runtime.NumCPU()

type bitmapContainerKey struct {
	key    uint16
	idx    int
	bitmap *Bitmap
}

type multipleContainers struct {
	key        uint16
	containers []container
	idx        int
}

type keyedContainer struct {
	key       uint16
	container container
	idx       int
}

type bitmapContainerHeap []bitmapContainerKey

func ( bitmapContainerHeap) () int           { return len() }
func ( bitmapContainerHeap) (,  int) bool { return [].key < [].key }
func ( bitmapContainerHeap) (,  int)      { [], [] = [], [] }

func ( *bitmapContainerHeap) ( interface{}) {
	// Push and Pop use pointer receivers because they modify the slice's length,
	// not just its contents.
	* = append(*, .(bitmapContainerKey))
}

func ( *bitmapContainerHeap) () interface{} {
	 := *
	 := len()
	 := [-1]
	* = [0 : -1]
	return 
}

func ( bitmapContainerHeap) () bitmapContainerKey {
	return [0]
}

func ( *bitmapContainerHeap) () ( uint16,  container) {
	 := .Peek()
	 = .key
	 = .bitmap.highlowcontainer.containers[.idx]

	 := .idx + 1
	if  < .bitmap.highlowcontainer.size() {
		 = bitmapContainerKey{
			.bitmap.highlowcontainer.keys[],
			,
			.bitmap,
		}
		(*)[0] = 
		heap.Fix(, 0)
	} else {
		heap.Pop()
	}

	return
}

func ( *bitmapContainerHeap) ( []container) multipleContainers {
	if .Len() == 0 {
		return multipleContainers{}
	}

	,  := .popIncrementing()
	 = append(, )

	for .Len() > 0 &&  == .Peek().key {
		_,  = .popIncrementing()
		 = append(, )
	}

	return multipleContainers{
		,
		,
		-1,
	}
}

func newBitmapContainerHeap( ...*Bitmap) bitmapContainerHeap {
	// Initialize heap
	var  bitmapContainerHeap = make([]bitmapContainerKey, 0, len())
	for ,  := range  {
		if !.IsEmpty() {
			 := bitmapContainerKey{
				.highlowcontainer.keys[0],
				0,
				,
			}
			 = append(, )
		}
	}

	heap.Init(&)

	return 
}

func repairAfterLazy( container) container {
	switch t := .(type) {
	case *bitmapContainer:
		if .cardinality == invalidCardinality {
			.computeCardinality()
		}

		if .getCardinality() <= arrayDefaultMaxSize {
			return .toArrayContainer()
		} else if .(*bitmapContainer).isFull() {
			return newRunContainer16Range(0, MaxUint16)
		}
	}

	return 
}

func toBitmapContainer( container) container {
	switch t := .(type) {
	case *arrayContainer:
		return .toBitmapContainer()
	case *runContainer16:
		if !.isFull() {
			return .toBitmapContainer()
		}
	}
	return 
}

func appenderRoutine( chan<- *Bitmap,  <-chan keyedContainer,  <-chan int) {
	 := -1
	 := 0
	var  []uint16
	var  []container
	for  !=  {
		select {
		case  := <-:
			if len() <= .idx {
				 = append(, make([]uint16, .idx-len()+1)...)
				 = append(, make([]container, .idx-len()+1)...)
			}
			[.idx] = .key
			[.idx] = .container

			++
		case  := <-:
			 = 
		}
	}
	 := &Bitmap{
		roaringArray{
			make([]uint16, 0, ),
			make([]container, 0, ),
			make([]bool, 0, ),
			false,
		},
	}
	for  := range  {
		if [] != nil { // in case a resulting container was empty, see ParAnd function
			.highlowcontainer.appendContainer([], [], false)
		}
	}

	 <- 
}

// ParHeapOr computes the union (OR) of all provided bitmaps in parallel,
// where the parameter "parallelism" determines how many workers are to be used
// (if it is set to 0, a default number of workers is chosen)
// ParHeapOr uses a heap to compute the union. For rare cases it might be faster than ParOr
func ( int,  ...*Bitmap) *Bitmap {

	 := len()
	if  == 0 {
		return NewBitmap()
	} else if  == 1 {
		return [0].Clone()
	}

	if  == 0 {
		 = defaultWorkerCount
	}

	 := newBitmapContainerHeap(...)

	 := make(chan *Bitmap)
	 := make(chan multipleContainers, 128)
	 := make(chan keyedContainer, 32)
	 := make(chan int)

	 := sync.Pool{
		New: func() interface{} {
			return make([]container, 0, len())
		},
	}

	 := func() {
		// Assumes only structs with >=2 containers are passed
		for  := range  {
			 := toBitmapContainer(.containers[0]).lazyOR(.containers[1])
			for ,  := range .containers[2:] {
				 = .lazyIOR()
			}
			 = repairAfterLazy()
			 := keyedContainer{
				.key,
				,
				.idx,
			}
			 <- 
			.Put(.containers[:0])
		}
	}

	go appenderRoutine(, , )

	for  := 0;  < ; ++ {
		go ()
	}

	 := 0
	for .Len() > 0 {
		 := .Next(.Get().([]container))
		if len(.containers) == 1 {
			 <- keyedContainer{
				.key,
				.containers[0],
				,
			}
			.Put(.containers[:0])
		} else {
			.idx = 
			 <- 
		}
		++
	}
	 <- 

	 := <-

	close()
	close()
	close()

	return 
}

// ParAnd computes the intersection (AND) of all provided bitmaps in parallel,
// where the parameter "parallelism" determines how many workers are to be used
// (if it is set to 0, a default number of workers is chosen)
func ( int,  ...*Bitmap) *Bitmap {
	 := len()
	if  == 0 {
		return NewBitmap()
	} else if  == 1 {
		return [0].Clone()
	}

	if  == 0 {
		 = defaultWorkerCount
	}

	 := newBitmapContainerHeap(...)

	 := make(chan *Bitmap)
	 := make(chan multipleContainers, 128)
	 := make(chan keyedContainer, 32)
	 := make(chan int)

	 := func() {
		// Assumes only structs with >=2 containers are passed
		for  := range  {
			 := .containers[0].and(.containers[1])
			for ,  := range .containers[2:] {
				if .isEmpty() {
					break
				}
				 = .iand()
			}

			// Send a nil explicitly if the result of the intersection is an empty container
			if .isEmpty() {
				 = nil
			}

			 := keyedContainer{
				.key,
				,
				.idx,
			}
			 <- 
		}
	}

	go appenderRoutine(, , )

	for  := 0;  < ; ++ {
		go ()
	}

	 := 0
	for .Len() > 0 {
		 := .Next(make([]container, 0, 4))
		if len(.containers) ==  {
			.idx = 
			 <- 
			++
		}
	}
	 <- 

	 := <-

	close()
	close()
	close()

	return 
}

// ParOr computes the union (OR) of all provided bitmaps in parallel,
// where the parameter "parallelism" determines how many workers are to be used
// (if it is set to 0, a default number of workers is chosen)
func ( int,  ...*Bitmap) *Bitmap {
	var  uint16 = MaxUint16
	var  uint16

	 := [:0]
	for ,  := range  {
		if !.IsEmpty() {
			 = append(, )
		}
	}
	 = 

	for ,  := range  {
		 = minOfUint16(, .highlowcontainer.keys[0])
		 = maxOfUint16(, .highlowcontainer.keys[.highlowcontainer.size()-1])
	}

	if  == MaxUint16 &&  == 0 {
		return New()
	} else if len() == 1 {
		return [0].Clone()
	}

	 := int() - int() + 1
	if  == 1 {
		// revert to FastOr. Since the key range is 0
		// no container-level aggregation parallelism is achievable
		return FastOr(...)
	}

	if  == 0 {
		 = defaultWorkerCount
	}

	var  int
	var  int
	if *4 > int() {
		 = 1
		 = int()
	} else {
		 =  * 4
		 = (int() +  - 1) / 
	}

	if * < int() {
		// it's fine to panic to indicate an implementation error
		panic(fmt.Sprintf("invariant check failed: chunkCount * chunkSize < keyRange, %d * %d < %d", , , ))
	}

	 := make([]*roaringArray, )

	 := make(chan parChunkSpec, minOfInt(maxOfInt(64, 2*), int()))
	 := make(chan parChunk, minOfInt(32, int()))

	 := func() {
		for  := range  {
			 := lazyOrOnRange(&[0].highlowcontainer, &[1].highlowcontainer, .start, .end)
			for ,  := range [2:] {
				 = lazyIOrOnRange(, &.highlowcontainer, .start, .end)
			}

			for ,  := range .containers {
				.containers[] = repairAfterLazy()
			}

			 <- parChunk{, .idx}
		}
	}

	for  := 0;  < ; ++ {
		go ()
	}

	go func() {
		for  := 0;  < ; ++ {
			 := parChunkSpec{
				start: uint16(int() + *),
				end:   uint16(minOfInt(int()+(+1)*-1, int())),
				idx:   int(),
			}
			 <- 
		}
	}()

	 := 
	for  := range  {
		[.idx] = .ra
		--
		if  == 0 {
			break
		}
	}
	close()
	close()

	 := 0
	for ,  := range  {
		 += .size()
	}

	 := Bitmap{
		roaringArray{
			containers:      make([]container, ),
			keys:            make([]uint16, ),
			needCopyOnWrite: make([]bool, ),
		},
	}

	 := 0
	for ,  := range  {
		copy(.highlowcontainer.containers[:], .containers)
		copy(.highlowcontainer.keys[:], .keys)
		copy(.highlowcontainer.needCopyOnWrite[:], .needCopyOnWrite)
		 += .size()
	}

	return &
}

type parChunkSpec struct {
	start uint16
	end   uint16
	idx   int
}

type parChunk struct {
	ra  *roaringArray
	idx int
}

func ( parChunk) () int {
	return .ra.size()
}

func parNaiveStartAt( *roaringArray,  uint16,  uint16) int {
	for ,  := range .keys {
		if  >=  &&  <=  {
			return 
		} else if  >  {
			break
		}
	}
	return .size()
}

func lazyOrOnRange(,  *roaringArray, ,  uint16) *roaringArray {
	 := newRoaringArray()
	 := .size()
	 := .size()

	 := parNaiveStartAt(, , )
	 := parNaiveStartAt(, , )

	var  uint16
	var  uint16
	if  <  &&  <  {
		 = .getKeyAtIndex()
		 = .getKeyAtIndex()

		for  <=  &&  <=  {

			if  <  {
				.appendCopy(*, )
				++
				if  ==  {
					break
				}
				 = .getKeyAtIndex()
			} else if  >  {
				.appendCopy(*, )
				++
				if  ==  {
					break
				}
				 = .getKeyAtIndex()
			} else {
				 := .getFastContainerAtIndex(, false)

				.appendContainer(, .lazyOR(.getContainerAtIndex()), false)
				++
				++
				if  ==  ||  ==  {
					break
				}

				 = .getKeyAtIndex()
				 = .getKeyAtIndex()
			}
		}
	}

	if  <  {
		 = .getKeyAtIndex()
		for  <=  {
			.appendCopy(*, )
			++
			if  ==  {
				break
			}
			 = .getKeyAtIndex()
		}
	}

	if  <  {
		 = .getKeyAtIndex()
		for  <=  {
			.appendCopy(*, )
			++
			if  ==  {
				break
			}
			 = .getKeyAtIndex()
		}
	}
	return 
}

func lazyIOrOnRange(,  *roaringArray, ,  uint16) *roaringArray {
	 := .size()
	 := .size()

	 := 0
	 := parNaiveStartAt(, , )

	var  uint16
	var  uint16
	if  <  &&  <  {
		 = .getKeyAtIndex()
		 = .getKeyAtIndex()

		for  <=  &&  <=  {
			if  <  {
				++
				if  >=  {
					break
				}
				 = .getKeyAtIndex()
			} else if  >  {
				.insertNewKeyValueAt(, , .getContainerAtIndex())
				.needCopyOnWrite[] = true
				++
				++
				++
				if  >=  {
					break
				}
				 = .getKeyAtIndex()
			} else {
				 := .getFastContainerAtIndex(, true)

				.containers[] = .lazyIOR(.getContainerAtIndex())
				.needCopyOnWrite[] = false
				++
				++
				if  >=  ||  >=  {
					break
				}

				 = .getKeyAtIndex()
				 = .getKeyAtIndex()
			}
		}
	}
	if  <  {
		 = .getKeyAtIndex()
		for  <=  {
			.appendCopy(*, )
			++
			if  >=  {
				break
			}
			 = .getKeyAtIndex()
		}
	}
	return 
}